'''
    给你一个头节点，返回二叉树的最大深度
    二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
'''

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def traverse(root):
            global res,depth
            if root is None:
                return None
            depth += 1
            if root.left is None and root.right is None:
                res = max(res,depth)

            traverse(root.left)
            traverse(root.right)
            depth -= 1
        
        res = 0
        depth = 0
        traverse(root)
        return res
    
    def maxDepth2(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left = self.maxDepth2(root.left)
        right = self.maxDepth2(root.right)

        res = max(left,right) + 1
        return res

        
        
